package com.example.demo.sort;

import java.util.Arrays;

/**
 * @author void
 * @date 2022/2/25 17:20
 * @desc 归并排序
 * https://www.cnblogs.com/guoyaohua/p/8600214.html
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {26,3,5,15,6,2};
        System.out.println(Arrays.toString(mergeSort(nums)));
    }
    
    public static int[] mergeSort(int[] array){
        if(array.length<2){
            return array;
        }
        int mid = array.length/2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(mergeSort(left), mergeSort(right));
    }
    
    public static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }
}
